1. Field of the Invention
This invention is intended for enlargement processing of an image represented with a multi-step graduation and relates in particular to an image processing apparatus, an image processing method, and an image processing program for performing the enlargement processing using a computer.
2. Description of the Related Art
Image enlargement processing is one type of basic signal processing for a digital image. For example, various high-quality image processing functions are demanded in fields such as database and high-definition color print, and image enlargement is demanded as one of the image processing functions. The image enlargement processing is one type of basic processing for a system such as editing, filing, displaying, and printing images. For example, to print out a digital image input externally on a printer different in resolution or display the digital image on an enlarged scale on a display, image enlargement processing is required.
In recent years, displaying or printing of such digital images with high quality has been demanded with distribution of digital cameras, scanners, electronic documents, and HTML (Hyper Text Markup Language) documents. The digital images have various resolutions and to output the digital image on a printer or display the digital image on a display, resolution conversion is required. Most of the digital images obtained via a network are low-resolution images; particularly in such a case, the high-quality enlargement art of the image becomes necessary.
For example, to output an image onto a 600-dpi printer, it becomes necessary to enlarge the image eight times. In recent years, distribution of inexpensive low-resolution digital cameras has been started; and to print a low-resolution image of 640×480 pixels photographed by such a digital camera, the image enlargement technology becomes one of the most important image processing. In addition, in output of a large-format print (poster image) and enlargement output of a part of a digital image, high-quality enlargement at a large enlargement ratio is demanded.
The enlargement processing is an extremely important function that can also be used as a resolution conversion technique required for connecting media different in resolution, such as an HDTV (high-definition television), an NTSC television, an electronic still camera, a medical image system, and a print image system. Further, in recent years, with the widespread of image data, mainly intended for display at a comparatively low resolution in the neighborhood of 75 dpi (display resolution) of an image on an Internet home page, digital video, the need for high-quality enlargement processing has also grown to produce the high-quality output result in printing the low-resolution images on a high-resolution printer.
Hitherto, a large number of techniques have been proposed as a technique of performing enlargement processing of a multilevel image represented with a multi-step gradation, namely, finding the values of pixel positions after enlargement. For example, enlargement techniques based on interpolation of nearest neighbor method, linear interpolation or bilinear method, cubic convolution method, which will be hereinafter also referred to as interpolation enlargement techniques, are well known.
The nearest neighbor method is a method of using as each pixel value after enlargement, the pixel value of the nearest pixel when each pixel is inversely mapped onto the original image. For example, letting the enlargement ratio in the x direction be a and that in the y direction be b, an inverse map point on the original image resulting from multiplying each coordinate point (X, Y) after enlargement by 1/a and 1/b is calculated and the pixel value on the original image nearest to the inverse map point is used as the pixel value of (X, Y).
The linear interpolation or bilinear method is a method of assuming that the pixel value between pixels changes linearly, referencing nearby pixels of the inverse map point of pixel after enlargement (for example, four nearby pixels), and performing linear approximation (linear interpolation) of the area surrounded by the pixel points (four points (four nearby pixels)) in the x direction and the y direction to find the pixel value at the inverse map point. The linear interpolation or bilinear method involves heavier processing load than the nearest neighbor method, but involves comparatively small computation amount and the linear interpolation itself produces the smoothing effect, so that jaggies are hard to be noticeable as compared with the nearest neighbor method.
The cubic convolution method is a method of defining an interpolation function approximating a sinc function {sinc(x)=sin(x)/x} based on a sampling theorem and performing convolution of nearby pixels of the inverse map point of pixel after enlargement (for example, 16 pixels (four by four pixels in the X direction and Y direction)) and the approximate interpolation function to find the pixel value after enlargement. This is based on the idea of suppressing aliasing distortion caused by resampling using the fact that the frequency characteristic of the sinc function is ideal, namely, it becomes “1” within Nyquist frequency and becomes “0” outside the Nyquist frequency. The method can provide a sharp image, so that the image quality is comparatively good as compared with the two methods described above.
However, the interpolation enlargement techniques tend to substantially cause the image to blur. Since the nearest neighbor method is easy processing and involves small computation amount, processing can be performed at high speed, but one pixel of the original image is enlarged intact to a rectangular shape. Thus, if the original image contains an oblique line or a boundary line, degradation of jaggies occurs in an edge or the oblique line portion in the enlarged image or if the magnification is large, the image becomes tessellar (blocky); the degree of visual image quality degradation is large.
The linear interpolation or bilinear method produces strong smoothing (low-pass filter (LPF)) effect. Thus, for example, LPF function is received centering on the edge portions not applied to the assumption of linear change, resulting in a smoothed image; the image becomes blurred as a whole. The cubic convolution method involves a large reference range and the computation amount is increased as compared with the two methods described above. Thus, the cubic convolution method is not appropriate when high-speed processing is required.
The sinc function, which is an infinitely continuous function, has a characteristic of high-frequency enhancement caused by use of the approximate function provided by discarding the sinc function in a predetermined range (−2 to 2 in the example of 16 pixels); light jaggies occur in edge portions and the noise component is enhanced although they are less than those of the nearest neighbor.
In contrast, recently, an enlargement technique of pixel value estimation type of estimating the pixel values of an enlarged image from information of the original image and preventing blurring, jaggies, or block distortion to occur has been proposed as an approach entirely different from the interpolation enlargement techniques described above. Some of the enlargement techniques of pixel value estimation type use IFS (Iterated Function System) of the concept of fractal (as described in Japanese Patent No. 2,968,582). Hereinafter, the enlargement technique of pixel value estimation type using the concept of fractal will be referred to as fractal enlargement technique.
The concept of fractal in digital image technologies is based on self-similarity assumption of an image on the premise that if a part of an image is taken out, another image resembling the taken-out image exists in the image in a different size and if necessary, in different orientation and different density. The fractal enlargement technique is a technique proposed coming with a fractal compression technique. Using the self-similarity of an image, about a minute rectangular area (called domain block) in an image, contraction, coordinate conversion of rotation or inversion in 90-degree units, and linear conversion of pixel values are performed from within the image. A search is made for the block most similar to the domain block (called range block), the image is divided according to the domain block, and the image is represented only by a set of the corresponding range block positions and coefficients of coordinate conversion and pixel value conversion used in the correspondence.
When the objective image is again formed from the set of the range block positions, coordinate conversion, and pixel value conversion, the operation of assigning the result of performing coordinate conversion and pixel value conversion to range block for any initial image to domain block is iterated. If the given number of iterations is reached or change caused by iteration becomes a threshold value or less, the processing is terminated and the image is reconstituted. The fact that as sufficient approximation of domain and range blocks is executed at the coding time, an image sufficiently close to the original image can be reconstituted is guaranteed by so-called collage theorem in the fractal theory. Such a fractal theory is described in detail in “Fractals Everywhere” (Michel F. Barnsley, Academic Press (1988)).
The fractal enlargement technique uses the self-similarity between block images different in size in an image and thus has the advantage that it does not depend on the resolution at the decoding time; it is an enlargement technique capable of also providing high-quality image output at a comparatively large enlargement ratio. For example, Japanese Patent No. 2,968,582 proposes a method of providing an enlarged image by repeating processing of finding the result of performing coordinate conversion and pixel value conversion for range block image enlarged at the same ratio as initial image is enlarged for any initial image of an enlargement size and replacing with enlarged domain block image position. In this method, the feature of fractal is utilized, jaggy occurrence is suppressed, and an enlarged image less blurred can be provided.
However, enlargement according to the fractal enlargement technique involves image quality problems of block distortion caused by discontinuity on domain block boundaries and noise and blurring caused by pattern crushing of a texture portion (busy portion) and further occurrence of noise-like garbage and fine-split-like pixel value staining although it is sharp for a binarily changing portion of a step edge part or of a document image.
For example, U.S. Pat. No. 6,141,017, JP-A-11-331595, and the like propose techniques as attempt to solve the image quality problems involved in the fractal enlargement technique.
U.S. Pat. No. 6,141,017 proposes a technique of preparing duplication of a domain block image and when assigning a range block, assigning only the inner portion of the range block to the corresponding inner portion of the domain block, thereby suppressing discontinuity occurring on the block image boundaries and a technique of separating block into an edge part and a flat part from scattering of pixel values in the block required when a pixel value conversion coefficient is found and performing enlargement processing with good edges by fractal enlargement while suppressing the picture-tinted flat part by using a different technique for the flat part. However, the technique still cannot solve degradation caused by noise-like garbage and fine-split-like pixel value staining in a step edge part or degradation of noise and blurring caused by pattern crushing of a texture portion (busy portion).
JP-A-11-331595 proposes a technique of performing both fractal enlargement and enlargement of linear interpolation or bilinear for an image and if the difference therebetween is small, adopting the result of the fractal enlargement and if the difference therebetween is large, adopting the result of the linear interpolation or bilinear or blending the results in response to the magnitude of the difference, thereby suppressing discontinuity on the block image boundaries. However, the technique tends to select the linear interpolation or bilinear in each edge portion where the difference between the fractal enlargement and the enlargement of linear interpolation or bilinear becomes large, and thus has disadvantage in that clear edge reproduction of the feature of fractal cannot be accomplished and blurring occurs.
Thus, the methods in the related arts for improving the fractal enlargement techniques separately present improvement on the image quality problems of blurring, jaggies, block distortion, etc., occurring when an enlarged image is provided, but the problems still are not totally solved. Particularly, it is difficult to provide an enlarged image with any other image quality performance enhanced while ensuring edge reproducibility.